package DynamicProgramming;

import java.util.*;

public class _740_DeleteandEarn {
    public int deleteAndEarn(int[] nums) {
        if(nums.length==0) return 0;
        Map<Integer, Integer> maps = new HashMap<>();
        for (int val : nums) {
            maps.put(val, maps.getOrDefault(val, 0) + 1);
        }
        List<Map.Entry<Integer,Integer>> res = new ArrayList<>(maps.entrySet());
        Collections.sort(res,(a,b)->a.getKey()-b.getKey());
        int len = res.size();
        int[] dp = new int[len];
        dp[0] = res.get(0).getValue() * res.get(0).getKey();
        int prev = res.get(0).getKey();
        for (int i = 1; i < len; i++) {
            int key = res.get(i).getKey();
            int val = res.get(i).getValue();
            if (key == prev + 1) {
                if (i - 2 > -1) {
                    dp[i] = Math.max(dp[i - 1], dp[i - 2] + key * val);
                } else {
                    dp[i] = Math.max(dp[i - 1], key * val);
                }
            } else {
                dp[i] = dp[i - 1] + key * val;
            }
            prev = key;
        }
        return dp[len - 1];
    }

    public int deleteAndEarn_1(int[] nums) {
        int len = 10001;
        int[] vals = new int[len];
        for (int i = 0; i < nums.length; i++) {
            vals[nums[i]] += nums[i];
        }
        int take = 0, skip = 0;
        for (int i = 0; i < len; i++) {
            int rtake = skip + vals[i];
            int rskip = Math.max(take, skip);
            take = rtake;
            skip = rskip;
        }
        return Math.max(take, skip);
    }
}
